#include <vector>
#include <set>
using namespace std;

#include <StraightOffsetPolygon.h>
#include <IntersectionConvexPolygons.h>
#include <MovingParticle.h>
#include <Graph.h>
#include <szMiscOperations.h>

StraightOffsetPolygon::StraightOffsetPolygon(const vector<MovingParticle*> vertices)
{
	particles = vertices;
	//set the neighborhood
	for (int i = 0; i < particles.size(); ++i)
	{
		MovingParticle* p = particles[i];
		MovingParticle* q = particles[i == particles.size() - 1 ? 0 : i + 1];
		MovingParticle* r = particles[i == 0 ? particles.size() - 1 : i - 1];
		MovingParticle::setNeighbors(p, r, q);
		pset.insert(p);
	}
	//calculate velocity if necessary
	for (int i = 0; i < particles.size(); ++i)
	{
		MovingParticle* p = particles[i];
		if (p->isInitialized()) continue;

		MovingParticle* q = particles[i == particles.size() - 1 ? 0 : i + 1];
		MovingParticle* r = particles[i == 0 ? particles.size() - 1 : i - 1];
		float vx, vy;
		calculateBisectorVelocity(r->getP(), p->getP(), q->getP(), vx, vy);
		p->setVelocity(vx, vy);
	}
	//find the next event for each particle.
	//we only need to compute for those whose event has not been set of its participants no longer part of this polygon.
	for (int i = 0; i < particles.size(); ++i)
	{
		MovingParticle* p = particles[i];
		EventStruct event = p->getEvent();
		if (event.type == UnknownEvent ||
			pset.find(event.q) == pset.end() ||
			pset.find(event.r) == pset.end())
		{
			//p->event = findNextEvent(p, particles);
		}
	}
}

/*
This function checks for a self-intersecting side of a polygon
*/
bool
simplePolygonCheck(vector<MovingParticle*>& particles)
{
	for (int i = 0; i < particles.size(); ++i)
	{
		CParticleF p = particles[i]->getP();
		CParticleF p2 = particles[i]->getNext()->getP();

		//NOTE: j starts j+2 to skip the adjacent side
		for (int j = i + 2; j < particles.size(); ++j)
		{
			CParticleF q = particles[j]->getP();
			CParticleF q2 = particles[j]->getNext()->getP();
			pair<float, float> param = _IntersectConvexPolygon::intersect(p, p2, q, q2);
			if (param.first>0 && param.first<1.0 && param.second>0 && param.second < 1.0)
			{
				return false;
			}
		}
	}
	return true;
}

void
_trace(Vertex<CParticleF>* u, Vertex<CParticleF>*prev, vector<MovingParticle*>& points)
{
	ParticleFactory* factory = ParticleFactory::getInstance();
	//MovingParticle* particle = factory->makeParticle(u->key, Initial, 0.0f);
	//points.push_back(particle);
	u->color = Black;
	CParticleF pu = u->key;
	CParticleF qu = prev == NULL ? CParticleF(pu.m_X - 1.0, pu.m_Y) : prev->key;
	int count = 0;
	while (true)
	{
		Vertex<CParticleF>* v = NULL;
		float minAngle = 2 * PI;
		//Walk in clock-wise  order.
		for (int i = 0; i < u->aList.size(); ++i)
		{
			Vertex<CParticleF>* w = u->aList[i]->v;
			if (w->color == White)
			{
				float ang = GetVisualAngle2(qu.m_X, qu.m_Y, w->key.m_X, w->key.m_Y, pu.m_X, pu.m_Y);
				if (ang <= 0) ang += 2 * PI;
				if (ang < minAngle)
				{
					minAngle = ang;
					v = w;
				}
			}
		}
		if (v != NULL)
		{
			count++;
			MovingParticle* particle2 = factory->makeParticle(u->key, Initial, 0.0f);
			points.push_back(particle2); //every branch will result in a new particle.
			_trace(v, u, points);
		}
		else
		{
			break;
		}
		qu = v->key; //update where we are coming from
	}
	//make a particle on the return path
	for (int i = count; i < 2; ++i)
	{
		MovingParticle* particle2 = factory->makeParticle(u->key, Initial, 0.0f);
		points.push_back(particle2);
	}
}

/*
Trace a forrest and create a polygon for each tree.
*/
vector<StraightOffsetPolygon>
traceForrest(vector<Vertex<CParticleF>*>& forrest)
{
	for (int i = 0; i < forrest.size(); ++i)
	{
		forrest[i]->Reset();
	}
	vector<StraightOffsetPolygon> polygons;
	while (true)
	{

		vector<MovingParticle*> points;
		for (int j = 0; j < forrest.size(); ++j)
		{
			if (forrest[j]->color == White)
			{
				_trace(forrest[j], NULL, points);
				//remove a copy of the first one at the end of the trace
				//points.erase(points.end() - 1);
				StraightOffsetPolygon poly(points);
				polygons.push_back(poly);
				break;
			}
		}
		if (points.empty())
		{
			break;
		}
	}
	return polygons;
}

/*vector<MovingParticle*>
Tree2OffsetPolygon(vector<Vertex<CParticleF>*>& tree, float margin, float eps)
{
	ParticleFactory* factory = ParticleFactory::getInstance();
	vector<MovingParticle*> points = _traceForest(tree);
	vector<MovingParticle*> poly;
	for (int i = 0; i < points.size(); ++i)
	{
		int i0 = (i - 1 + points.size()) % points.size();
		int i2 = (i + 1) % points.size();
		CParticleF o = points[i]->p;
		CParticleF a = points[i0]->p;
		CParticleF b = points[i2]->p;
		if (Distance(a, o) < eps || Distance(b, o) < eps)
		{
			continue;
		}
		if (Distance(a, b) > eps)
		{
			MovingParticle* particle = factory->makeParticle(o, Regular, 0.0f); //points[i];
			particle->calculateVelocity();
			setRelation(points[i], particle);
			poly.push_back(particle);
		}
		else //this is a leaf node of the tree.
		{
			float ang = GetVisualDirection(o.m_X, o.m_Y, a.m_X, a.m_Y);
			float angles[] = { ang + PI / 4.0, ang - PI / 4.0 };
			MovingParticle* q[2];
			q[0] = points[i];
			q[1] = factory->makeParticle(o, Regular, 0.0f);
			for (int j = 0; j < 2; ++j)
			{
				float vx = sqrt(2.0) * cos(angles[j]);
				float vy = sqrt(2.0) * sin(angles[j]);
				MovingParticle* particle = factory->makeParticle(o, Regular, 0.0f);
				particle->setVelocity(vx, vy);
				setRelation(points[i], particle);
				poly.push_back(particle);
			}
		}
	}
	for (int i = 0; i < poly.size(); ++i)
	{
		//setting the neighbors, except velocity
		int j = (i + 1) % poly.size();
		int k = (i - 1 + poly.size()) % poly.size();
		MovingParticle* p = poly[i];
		MovingParticle* prev = poly[k];
		MovingParticle* next = poly[j];
		setNeighbors(p, prev, next);
	}
	for (int i = 0; i < poly.size(); ++i)
	{
		poly[i]->update(margin);
	}
	return poly;
}*/
